#include <stdio.h>
#include <stdlib.h>

#define kMaxStackSize 100 /* 栈的最大容量 */
/* 配对符号类型。依次对应： */
/* 程序结尾、左注释、右注释、{、}、[、]、(、)、其它符号 */
typedef enum { end, lc, rc, lbrc, rbrc, lbrkt, rbrkt, lpr, rpr, others } Token;
typedef Token SElemSet; /* 栈中元素类型为Token */

/* 顺序栈的定义及操作参见代码3-1至3-5，此处略去 */
typedef enum {false, true} bool;
#define NIL -1
typedef int Position; /* 整型下标，表示元素的位置 */
typedef struct StackNode *Stack;
struct StackNode {
    int capacity; /* 顺序栈的容量 */
    Position top; /* 顺序栈的栈顶指针，初始化为-1 */
    SElemSet *data; /* 存储数据的数组 */
};
void InitStack(Stack stack, int kMaxSize);
bool IsFull(Stack stack);
bool IsEmpty(Stack stack);
void Push(Stack stack, SElemSet x);
SElemSet Top(Stack stack);
void Pop(Stack stack);
void DestroyStack(Stack stack);
/* 顺序栈结束 */

/* 匹配结果类型，依次对应：匹配成功、左半符不匹配、右半符不匹配 */
typedef enum { ok, left_no_match, right_no_match } ErrorCode;
typedef struct ResultNode *Result;
struct ResultNode { /* 符号匹配结果存储结点 */
    ErrorCode code; /* 匹配结果 */
    Token token; /* 匹配不成功的符号类型 */
};

Token GetToken(char c);
bool IsMatched(Token left, Token right);
Result SymbolMatching();
void PrintSymbol(Token token);

int main(void) {
    Result result;

    result = SymbolMatching(); /* 读入程序并执行匹配 */
    if (result->code == ok) { /* 若匹配成功 */
        printf("YES\n");
    } else { /* 若匹配不成功 */
        printf("NO\n");
        if (result->code == left_no_match) { /* 左半符不匹配 */
            PrintSymbol(result->token);
            printf("-?\n");
        } else { /* 右半符不匹配 */
            printf("?-");
            PrintSymbol(result->token);
            printf("\n");
        }
    }
    return 0;
}

Token GetToken(char c) {
    /* 从输入中读取并返回一个符号类型    */
    /* 外部调用方法：GetToken(getchar()) */
    Token ret; /* 返回的符号类型 */

    ret = others; /* 默认符号类型为其它 */
    switch (c) {
    case '{':
        ret = lbrc;
        break;
    case '[':
        ret = lbrkt;
        break;
    case '(':
        ret = lpr;
        break;
    case '}':
        ret = rbrc;
        break;
    case ']':
        ret = rbrkt;
        break;
    case ')':
        ret = rpr;
        break;
    case '/': /* 多读一个符号，判断是否左注释 */
        c = getchar();
        if (c == '*')
            ret = lc;
        else
            ret = GetToken(c); /* 若不是左注释，需要判断当前c的类型 */
        break;
    case '*': /* 多读一个符号，判断是否右注释 */
        c = getchar();
        if (c == '/')
            ret = rc;
        else
            ret = GetToken(c); /* 若不是右注释，需要判断当前c的类型 */
        break;
    case '\n': /* 判断是否程序末尾 */
        c = getchar();
        if (c == '.') { /* 如果回车跟一个句点，则检查后面是否跟着一个回车 */
            c = getchar();
            if (c == '\n')
                ret = end;
        }
        if (ret != end)
            ret = GetToken(c); /* 若不是结尾，则需要判断当前c的类型*/
        break;
    default:
        break;
    }
    return ret;
}

bool IsMatched(Token left, Token right) {
    /* 判断左右符号是否在类型中相邻 */
    return (right == (left + 1));
}

void PrintSymbol(Token token) {
    /* 根据token类型输出符号 */
    switch (token) {
    case lc:
        printf("/*");
        break;
    case lbrc:
        printf("{");
        break;
    case lbrkt:
        printf("[");
        break;
    case lpr:
        printf("(");
        break;
    case rc:
        printf("*/");
        break;
    case rbrc:
        printf("}");
        break;
    case rbrkt:
        printf("]");
        break;
    case rpr:
        printf(")");
        break;
    default:
        break;
    }
}

Result SymbolMatching() {
    /* 读入表达式，检查指定符号是否都能匹配 */
    /* 匹配结果存在result中返回 */
    Stack stack; /* 辅助栈 */
    Token token; /* 表达式中解析出的符号 */
    Result result; /* 匹配结果 */

    stack = (Stack)malloc(sizeof(struct StackNode));
    InitStack(stack, kMaxStackSize); /* 初始化一个顺序栈 */
    result = (Result)malloc(sizeof(struct ResultNode));
    result->code = ok; /* 默认匹配结果是成功的 */
    token = GetToken(getchar()); /* 获取一个符号类型 */
    while (token != end) { /* 一直处理到程序结尾 */
        switch (token) { /* 根据符号类型处理 */
        /* 如果是左半符 */
        case lc:
        case lbrc:
        case lbrkt:
        case lpr:
            Push(stack, token); /* 压入栈中暂存 */
            break;
        /* 如果是右半符 */
        case rc:
        case rbrc:
        case rbrkt:
        case rpr:
            /* 若有右半符但存左半符的栈已空 */
            if (IsEmpty(stack) == true) {
                result->code = right_no_match; /* 右半符不匹配 */
                result->token = token; /* 存储失配的右半符 */
            } /* 若栈不空但左右符号不匹配 */
            else if (IsMatched(Top(stack), token) == false) {
                result->code = left_no_match; /* 左半符不匹配 */
                result->token = Top(stack); /* 栈顶是失配的左半符 */
            } else { /* 匹配成功 */
                Pop(stack); /* 消掉一对 */
            }
            break;
        default:
            break;
        }
        if (result->code != ok) { /* 若发现不匹配 */
            break; /* 则跳出循环 */
        }
        token = GetToken(getchar()); /* 否则继续获取下一个符号类型 */
    }
    /* 虽然前面的匹配都成功，但最后栈不为空 */
    if (result->token == ok && IsEmpty(stack) == false) {
        result->code = left_no_match; /* 有多余的左半符不匹配 */
        result->token = Top(stack); /* 栈顶是失配的左半符 */
    }
    DestroyStack(stack);

    return result;
}

void InitStack(Stack stack, int kMaxSize) {
    /* 初始化一个大小为kMaxSize的顺序栈 */
    stack->capacity = kMaxSize;
    stack->top = -1;
    stack->data = (SElemSet *)malloc(sizeof(SElemSet) * kMaxSize);
}

bool IsFull(Stack stack) {
    /* 判断栈是否已满 */
    if ((stack->top + 1) == stack->capacity)
        return true;
    else
        return false;
}

bool IsEmpty(Stack stack) {
    /* 判断栈是否为空 */
    if (stack->top == -1)
        return true;
    else
        return false;
}

void Push(Stack stack, SElemSet x) {
    /* 入栈 */
    if (IsFull(stack)) {
        printf("错误：栈已满。\n");
    } else {
        stack->top++;
        stack->data[stack->top] = x;
    }
}

SElemSet Top(Stack stack) {
    /* 取顶 */
    if (IsEmpty(stack)) {
        printf("错误：栈为空。\n");
        return NIL;
    } else {
        return stack->data[stack->top];
    }
}

void Pop(Stack stack) {
    /* 出栈 */
    if (IsEmpty(stack)) {
        printf("错误：栈为空。\n");
    } else {
        stack->top--;
    }
}

void DestroyStack(Stack stack) {
    /* 释放栈空间 */
    free(stack->data);
    free(stack);
}